---
title: "排列数字"
created: 2025-11-28
tags:
  - 算法
---

# 排列数字

## 题目 [排列数字](https://www.acwing.com/problem/content/844/)

![[image-abb92975.png]]

## 思路分析

最暴力的写法

枚举每一位可放的数 有几位就得写几重循环

```cpp
#include<bits/stdc++.h>

using namespace std;

#define lf else if

int main(){

    int n;

    cin>>n;

    if(n==1){cout<<"1";}

    if(n==2)cout<<"1 2\n2 1";

    if(n==3)cout<<"1 2 3\n1 3 2\n2 1 3\n2 3 1\n3 1 2\n3 2 1";

    if(n==4){

        for(int i = 1;i<=n;i++){

            for(int j = 1;j<=n;j++){

                for(int k = 1;k<=n;k++){

                    for(int l = 1;l<=n;l++){

                        if(i+j+k+l==10&&i*k*j*l==24)printf("%d %d %d %d\n",i,j,k,l);

                    }

                }

            }

        }

    }

    if(n==5){

        for(int i = 1;i<=n;i++){

            for(int j = 1;j<=n;j++){

                for(int k = 1;k<=n;k++){

                    for(int l = 1;l<=n;l++){

                        for(int a = 1;a<=n;a++){

                            if(i+j+k+l+a==15&&i*k*j*l*a==120)printf("%d %d %d %d %d\n",i,j,k,l,a);

                        }

                    }

                }

            }

        }

    }

    if(n==6){

        for(int i = 1;i<=n;i++){

            for(int j = 1;j<=n;j++){

                for(int k = 1;k<=n;k++){

                    for(int l = 1;l<=n;l++){

                        for(int a = 1;a<=n;a++){

                            for(int b = 1;b<=n;b++){

                                if(i+j+k+l+a+b==21&&i*k*j*l*a*b==720)printf("%d %d %d %d %d %d\n",i,j,k,l,a,b);

                            }

                        }

                    }

                }

            }

        }

    }

    else{

        for(int i = 1;i<=n;i++){

            for(int j = 1;j<=n;j++){

                for(int k = 1;k<=n;k++){

                    for(int l = 1;l<=n;l++){

                        for(int a = 1;a<=n;a++){

                            for(int b = 1;b<=n;b++){

                                for(int c = 1;c<=n;c++)if(i+j+k+l+a+b+c==28&&i*k*j*l*a*b*c==5040)printf("%d %d %d %d %d %d %d\n",i,j,k,l,a,b,c);

                            }

                        }

                    }

                }

            }

        }

    }

    return 0;

}
```

但发现其实有些性质 前一位放了某个数 后一位能放的数就受到了限制

其实可以按每一位来处理

首先看第一位能有哪些种情况 第一位确定后 再看第二位可以放哪些 以此类推 若推到最后达到n位了 就说明这种情况成立了

可以抽象成一棵递归搜索树

![[image-ad7a08c6.png]]

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=10;

int path[N];

bool st[N];

int n;

void dfs(int u,int n){

    if(u==n){

        for(int i=0;i<n;i++)

            cout<<path[i]<<" ";

        cout<<endl;

        return;

    }

    for(int i=1;i<=n;i++){

        if(!st[i]){

            st[i]=true;

            path[u]=i;

            dfs(u+1,n);

            path[u]=0;

            st[i]=false;

        }

    }

}

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>n;

    dfs(0,n);

    return 0;

}
```

用path数组记录每一位（u代表当前位） 用st数组记录某个数是否在前面已经被用过 然后从第0层开始递归 首先看的是第0位（第一位）能放什么
在1~n里面选 如果某个数没被用过 就可以选这个数 再看第0位确定了这个数之后有哪些选法 要把这个数标记选过了 且 进入u+1层继续看能选哪些数……

这类问题有个库函数 next\_permutation 可以解决

```cpp
#include<bits/stdc++.h>

using namespace std;

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n;cin>>n;

    vector<int> all;

    for(int i=1;i<=n;i++)

        all.push_back(i);

    do{

        for(int num:all)

            cout<<num<<" ";

        cout<<endl;

    }while(next_permutation(all.begin(),all.end()));

    return 0;

}
```

## 代码实现

```

```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/DFS/全排列（考虑顺序）/带分数|带分数]] 🏠 [[00-刷题理模型]] ➡️ [[火星人|火星人]]